|
In modular arithmetic, the modular multiplicative inverse of an integer ''a'' modulo ''m'' is an integer ''x'' such that : That is, it is the multiplicative inverse in the ring of integers modulo ''m'', denoted . Once defined, ''x'' may be noted , where the fact that the inversion is m-modular is implicit. The multiplicative inverse of ''a'' modulo ''m'' exists if and only if ''a'' and ''m'' are coprime (i.e., if ).〔.〕 If the modular multiplicative inverse of ''a'' modulo ''m'' exists, the operation of division by ''a'' modulo ''m'' can be defined as multiplying by the inverse of ''a'', which is in essence the same concept as division in the field of reals. ==Example== Suppose we wish to find modular multiplicative inverse ''x'' of 3 modulo 11. : This is the same as finding ''x'' such that : Working in we find one value of ''x'' that satisfies this congruence is 4 because : and there are no other values of ''x'' in that satisfy this congruence. Therefore, the modular multiplicative inverse of 3 modulo 11 is 4. Once found the inverse of 3 in , other values of ''x'' in can be found that also satisfy the congruence. They may be found by adding multiples of to the found inverse. Generalizing, all possible ''x'' for this example can be formed from : yielding . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「modular multiplicative inverse」の詳細全文を読む スポンサード リンク
|